//class Solution {
//public:
//    bool wordBreak(string s, vector<string>& wordDict) {
//        unordered_map<string, bool> hash;
//        for (auto& str : wordDict)
//        {
//            hash[str] = true;
//        }
//        int n = s.size();
//        s = ' ' + s;
//        vector<bool> dp(n + 1);
//        dp[0] = true;
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = i; j >= 1; j--)
//            {
//                if (hash[s.substr(j, i - j + 1)] == true && dp[j - 1])
//                {
//                    dp[i] = true;
//                    break;
//                }
//            }
//        }
//        return dp[n];
//    }
//};



//class Solution {
//public:
//    int lengthOfLIS(vector<int>& nums) {
//        int n = nums.size(), ret = 1;
//        vector<int> dp(n + 1, 1);
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = i - 1; j >= 0; j--)
//            {
//                if (nums[i] > nums[j])
//                    dp[i] = max(dp[i], dp[j] + 1);
//            }
//            ret = max(ret, dp[i]);
//        }
//        return ret;
//    }
//};



//class Solution {
//public:
//    int wiggleMaxLength(vector<int>& nums) {
//        int n = nums.size(), ret = 1;
//        vector<int> f(n, 1), g(n, 1);
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = i - 1; j >= 0; j--)
//            {
//                if (nums[j] < nums[i])
//                    f[i] = max(f[i], g[j] + 1);
//                if (nums[j] > nums[i])
//                    g[i] = max(g[i], f[j] + 1);
//            }
//            ret = max(ret, max(f[i], g[i]));
//        }
//        return ret;
//    }
//};


